Game

Time Limit: 20 Sec Memory Limit: 512 MB

Description

从前有个游戏。游戏分为 k 轮。

给定一个由小写英文字母组成的字符串的集合 S，

在每轮游戏开始时，双方会得到一个空的字符串，

然后两人轮流在该串的末尾添加字符，并且需要保证新的字符串是 S 中某个串的前缀，直到有一方不能操作，则不能操作的一方输掉这一轮。

新的一轮由上一轮输的人先手，最后一轮赢的人获得游戏胜利。

假定双方都采取最优策略，求第一轮先手的一方能否获胜。

Input

输入包含多组数据。

每组数据的第一行包含两个整数 n,k，分别表示字符串的数量和游戏的轮数。

接下来 n 行，每行一个由小写英文字母组成的字符串。

Output

对于每组数据输出一行，若先手能获胜输出 HY wins!，否则输出 Teacher wins!

Sample Input

2 3
　　a
　　b
　　3 1
　　a
　　b
　　c

Sample Output

HY wins!
　　HY wins!

HINT

1 ≤ n ≤ 1e5,1 ≤ k ≤ 1e9，保证所有字符串长度不超过 1e5，数据组数不超过 10。

Solution

img

显然Trie上这个DP显然就是为了求：一轮中，先手是否必胜或者必败。显然，一个点如果可以走向必败点那么就可以必胜。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;
typedef unsigned int u32;

const int ONE = 1e6 + 5;

int n, k;
char s[ONE];
int next[ONE][27], total, root = 1;
int f[ONE], g[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Insert()
{
    scanf("%s", s + 1);
    int u = root, n = strlen(s + 1);
    for(int i = 1; i <= n; i++)
    {
        int c = s[i] - 'a' + 1;
        if(!next[u][c]) next[u][c] = ++total;
        u = next[u][c];
    }
}

void Dfs_f(int u)
{
    if(!u) return;
    int PD = 1;
    for(int c = 1; c <= 26; c++) if(next[u][c]) {PD = 0; break;}
    if(PD) {g[u] = 0; return;}

    PD = 0;
    for(int c = 1; c <= 26; c++)
    {
        Dfs_f(next[u][c]);
        if(next[u][c] && f[next[u][c]] == 0) PD = 1;
    }
    f[u] = PD;
}

void Dfs_g(int u)
{
    if(!u) return;
    int PD = 1;
    for(int c = 1; c <= 26; c++) if(next[u][c]) {PD = 0; break;}
    if(PD) {g[u] = 1; return;}

    PD = 0;
    for(int c = 1; c <= 26; c++)
    {
        Dfs_g(next[u][c]);
        if(next[u][c] && g[next[u][c]] == 0) PD = 1;
    }
    g[u] = PD;
}

int main()
{
    while(scanf("%d %d", &n, &k) != EOF)
    {
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        memset(next, 0, sizeof(next));
        total = 1;
        for(int i = 1; i <= n; i++)
            Insert();
        Dfs_f(1);    Dfs_g(1);
        if(f[1] == 1 && g[1] == 1) printf("HY wins!\n");
        else
            if(f[1] == 1)
                k % 2 == 1 ? printf("HY wins!\n") : printf("Teacher wins!\n");
        else
            printf("Teacher wins!\n");
    }
}